1. Field of the Invention
This invention relates generally to the field of computer graphics, and more particularly to a method for ordering objects that occupy a co-incident surface.
2. Description of the Related Art
Modem computer systems are widely used to model and render three-dimensional (3D) objects on two-dimensional (2D) display screens. For example, a variety of jobs that were usually drawn by hand (e.g., movie animation, architectural drawings, engineering drafting) are now performed with sophisticated computer graphics applications. These modern 3D computer graphics applications are able to render 3D images of not only a single fixed image, but also render views of the image dynamically as viewpoint and direction are changed. The term xe2x80x9cviewpointxe2x80x9d refers to the point at which the viewer is located and is sometimes referred to as camera position, eye position, center of projection, or the like. The term xe2x80x9cview directionxe2x80x9d refers to the direction of view from the viewpoint and is commonly referred to as camera direction, eye direction, direction of projection, or the like. As the viewpoint and view direction change from one frame to the next, the 3D images are rendered dynamically to reflect the scene relative to the new viewpoint and the direction.
The changes in viewpoint and direction may occur in several forms in 3D viewing. For example, an object in a 3D space may be viewed from any spatial position: front, back, above, below, or side. Furthermore, an object such as a building, sphere, or the like may be viewed from the inside or outside of the object. These changes in viewpoint and direction directly affect the way an object is to be described and rendered.
For example, in 3D computer graphics, two or more objects are often drawn on a same plane in space when they essentially lie on the same plane. FIG. 1A illustrates a perspective view of a table 102 with a plurality of cards 106. The cards 106 are placed on a top surface 104 of the table 102. When viewed from a view direction 108 above the table 102, the cards 106 appear on top of the surface 104 of the table 102. However, when viewed from a view direction 110 below the table 102, the cards 106 are not visible. Similarly, FIG. 1B shows a road surface 120 having a plurality of median stripes 122 painted thereon. The stripes 122 are visible when viewed from a view direction 124 above the road surface 120. On the other hand, they are not visible when viewed from a view direction 126 below the road surface.
In rendering the table 102 with the cards 106 or the road surface 120 with the stripes 122, conventional techniques have typically modeled the cards 106 and the surface 104 of the table 102 or the stripes 122 and the road surface 120 as co-planar polygons. Rendering these objects as being co-planar polygons, however, produces jitter about the co-planar regions. Since the layers are co-planar, the question xe2x80x9cwhich layer is in front?xe2x80x9d has no single answer. So algorithms that advance pixel-by-pixel across the screen, rendering the front-most surface at each pixel, are subject to error. Each pixel""s query may return any answer, and adjacent pixels may display colors from different layers in the surface. This visual discontinuity across the surface is commonly referred to as jitter, z-tearing, or z-buffer tearing. If no enhancements are made from the basic algorithm, then techniques such as ray-tracing and z-buffer rendering will produce errors. The set of techniques that produce these errors, however, is not restricted to those of ray-tracing and z-buffer rendering. In some instances, the mathematical modeling of the co-planar polygons leads to z-buffer tearing or other degrading artifacts.
Additionally, the conventional methods have suffered from discontinuous or choppy images. For example, in one frame, the card 106 may appear to be over the top surface 104 of the table 102. In another frame, the card 106 may actually appear to be under the table 102. The inconsistent rendering of the objects thus degrades graphics image quality and produces unrealistic images.
To address such problems, one method has rendered two or more co-planar objects by rendering one object slightly above or below the other object. While this solution improves the jitter effects, it is highly sensitive to the separation distance between the two objects. For instance, if the distance between the two objects is too far, one object may appear to be floating over or hanging below the other due to the separation between them. On the other hand, if the distance were too small, the previously described jitter effect may be produced. In either case, the resulting image would not accurately convey the desired effect of one object resting upon another.
Another method has implemented a fixed stacking order technique. This method specifies the order of a number of layers (e.g., co-planar objects) and then renders the layers in the specified order. FIG. 2A shows a node tree 200 depicting a fixed stacking order 202. The node tree 200 comprises a layer group node 204, which branches out to a plurality of nodes 206, 208, 210, and 212. The nodes 206, 208, 210, and 212 represent layer xe2x80x9cA,xe2x80x9d layer xe2x80x9cB,xe2x80x9d layer xe2x80x9cC,xe2x80x9d and layer xe2x80x9cD,xe2x80x9d respectively. The node tree specifies the stacking order 202 from left to right, i.e., from layer xe2x80x9cAxe2x80x9d to layer xe2x80x9cD.xe2x80x9d Accordingly, the node tree 200 is traversed in the order of nodes 206, 208, 210, and 212 to render the layers from the lowest to the highest layer. Each layer is allowed to draw over any previous layer at all points, without comparing the relative distance from the eye. The result is layers that appear to lie correctly atop each other.
FIG. 2B illustrates an orthographic view of the stacking order 202 of the layers xe2x80x9cA,xe2x80x9d xe2x80x9cB,xe2x80x9d xe2x80x9cC,xe2x80x9d and xe2x80x9cD.xe2x80x9d As shown, the layers are specified and rendered from back to front, i.e., from lowest to the highest. Thus, the lowest layer xe2x80x9cAxe2x80x9d is rendered first, then the second layer xe2x80x9cBxe2x80x9d is rendered on top of layer xe2x80x9cA.xe2x80x9d Next, the third layer xe2x80x9cCxe2x80x9d is drawn over layer xe2x80x9cBxe2x80x9d and finally, the highest layer xe2x80x9cDxe2x80x9d is rendered over the layer xe2x80x9cC.xe2x80x9dUnfortunately however, the fixed order of the conventional method does not allow rendering of a surface having two distinct sides from two distinct viewpoints. This is because the stacking order is fixed regardless of changes in view parameters such as viewpoint, view direction, or the like. For example, the stacking order 202 of FIGS. 2A and 2B only provides back-to-front drawing order of a surface and thus does not provide for jitter-free rendering of the other side of the surface as viewed from the opposite side. Hence, the problem of rendering co-planar or co-incident surface layers from other viewpoints is not adequately addressed by the conventional method.
In view of the foregoing, what is needed is a method for specifying and changing the ordering of co-planar or co-incident surface layers in response to changes in viewpoint or view direction without undesirable jitter or aliases.
The present invention fills these needs by providing method and system for determining view dependent ordering of geometry layers that occupy a co-incident surface. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, a method, or a computer readable medium. Several inventive embodiments of the present invention are described below.
In one embodiment, the present invention provides a method for determining view dependent ordering of geometry layers that occupy a co-incident surface. The co-incident surface has a first side and a second side, and is capable of being viewed on either side. In this method, a first order of the geometry layers is defined as viewed on the first side of the co-incident surface. In response to a specified view, a rendering order of the geometry layers is determined from the first order. The rendering order specifies an actual rendering sequence of the geometry layers. In one embodiment, the rendering order is the first order when the specified view is directed on the first side of the co-incident surface and is a reversed order of the first order when the specified view is directed on the second side of the co-incident surface.
In another embodiment, a method is provided for rendering geometry layers that occupy a co-incident surface relative to a view. The co-incident surface has a first side and an opposing second side. The co-incident surface is capable of being viewed on either side of the co-incident surface. The method includes: (a) defining a first order of the geometry layers as viewed on the first side of the co-incident surface; (b) receiving a specified view directed on either the first or second side; (c) determining a rendering order of the geometry layers from the first order in response to the specified view, wherein the rendering order specifies an actual rendering sequence of the plurality of geometry layers; and (d) rendering the geometry layers in the rendering order.
In yet another embodiment, the present invention provides a computer system for determining view dependent ordering of geometry layers that occupy a co-incident surface. The co-incident surface has a first side and a second side. The co-incident surface is capable of being viewed on either side of the co-incident surface. The system includes a bus, a processor coupled to the bus, and a memory coupled to the bus. The system also includes means for defining a first order of the geometry layers as viewed on the first side of the co-incident surface. In addition, the system includes means for determining a rendering order of the geometry layers from the first order in response to a specified view, wherein the rendering order specifies an actual rendering sequence of the plurality of geometry layers.
By thus providing a flexible rendering order based on a view-dependent stacking order, the present invention allows the co-incident layers to be rendered dynamically from one frame to another in a proper order without artifacts or aliases despite substantial changes in the view or geometry parameters. Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.